#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

// 部分背包问题:
// 现有重量为【4， 6， 3， 7， 1】，价值为【5， 7， 3， 9， 2】的物品，要求装入到容量为c的背包中，可以只装入物品的一部分，求出能装的价值最大值

struct Product{
    double getPrice() const
    {
        return v * 1.0 / w;
    }    

    bool operator>(const Product &rhs) const{ 
        return getPrice() > rhs.getPrice(); 
    }

    int id;
    int w;
    int v;
};

void solution(const vector<int> &w, const vector<int> &v, int c)
{
    vector<Product> prods(w.size(), Product());
    vector<int> tmp(w.size(), 0);
    for(int i{}; i < w.size(); i++){
        prods[i].id = i;
        prods[i].w = w[i];
        prods[i].v = v[i];
    } 

    std::sort(prods.begin(), prods.end(), [](const Product &l, const Product &r){return l.getPrice() > r.getPrice();});

    double total{};
    for(int i{}; i < prods.size(); i++){
        if(prods[i].w <= c){
            total += prods[i].v;
            c -= prods[i].w;
            tmp[i] = 1;
        }else{
            int pre = total;
            total += prods[i].v * (c * 1.0 / prods[i].w);
            c = 0;
            if(pre != total) tmp[i] = 1;
            break;
        }
    }

    
    for(auto prod: prods){
        cout << prod.w << ", " << prod.v << endl;
    }

    cout << "total: " << total << endl;
    for(auto i: tmp){
        cout << i << " ";
    }
    cout << endl;
}

int main(int args, char *argv[])
{
    solution({4, 6, 3, 7, 1}, {5, 7, 3, 9, 2}, 13);
    return 0;
}